A fully homomorphic encryption scheme allows the computation of arbitrary functions over encrypted data without requiring the use of a decryption key. However, actually constructing a fully homomorphic encryption scheme was a major open problem in cryptography for over 30 years, since 1978. This application will describe (among other things) a bootstrappable homomorphic encryption scheme, which can be used to construct (the first) fully homomorphic encryption scheme. However, first we provide some background.
A (regular) (public-key) encryption scheme allows for the encryption and decryption of data. More formally, a public-key encryption scheme has three procedures: KeyGen, Encrypt and Decrypt. A user uses the KeyGen procedure to generate its secret and public keys sk and pk, and it publishes its public key pk so that other parties can easily obtain it. Later, when a sender wants to send an encrypted message m to the user, the sender computes a ciphertext using the Encrypt procedure with the user's public key: c←Encrypt(pk, m). The user uses its secret key to recover the message from the ciphertext m←Decrypt(sk, c).
A homomorphic encryption scheme has all of the properties of a regular encryption scheme. However, it also allows anyone to modify what it is encrypted, even without the secret key. For example, an additively homomorphic encryption scheme allows anyone to do the following. Suppose ciphertext c1 encrypts the message m1 under public key pk, and ciphertext c2 encrypts the message m2 under pk. Then, given c1, c2, and pk, anyone can compute a ciphertext c that encrypts m1+m2 under pk. When we say “anyone” can do this, we mean in particular that the new ciphertext c can be computed efficiently without knowing sk. (Of course, computing c with sk is easy: using sk, one can use Decrypt to recover m1 and m2 from c1 and c2, and then one can set c←Encrypt(pk, m1+m2).) A multiplicatively homomorphic encryption scheme allows anyone to use c1, c2, and pk to compute a ciphertext c that encrypts m1×m2 under pk.
The essence of a fully homomorphic encryption (FHE) scheme is that it allows any function of the data or messages to be evaluated, while this data remains encrypted—not merely the addition function or the multiplication function. More formally, given ciphertexts that encrypt π1, . . . , πt, fully homomorphic encryption should allow anyone (not just the key-holder) to output a ciphertext that encrypts ƒ(π1, . . . , πt) for any desired function ƒ, as long as that function can be efficiently computed. No information about π1, . . . , πt or ƒ(π1, . . . , πt), or any intermediate plaintext values, should leak; the inputs, output and intermediate values are always encrypted. More specifically, in addition to the usual algorithms KeyGen, Encrypt, and Decrypt of an encryption scheme, a fully homomorphic encryption scheme ε also has an efficient algorithm Evaluateε that, for any valid public key pk, any circuit C (which represents the function ƒ that you want to be computed), and any ciphertexts ψi←Encryptε(pk, πi), outputsψ←Evaluateε(pk,C,ψ1, . . . ,ψt),a valid encryption of C(π1, . . . , πt) under pk. By a valid encryption of C(π1, . . . , πt) under pk, we mean that Decrypt(sk, ψ)=C(π1, . . . , πt). We say that an encryption scheme is fully homomorphic if Evaluate works correctly for any circuit C. That is, for any function ƒ that can be performed efficiently on unencrypted data (and it was already well-known that such a function can be computed efficiently via a boolean circuit C), that function can be performed efficiently on encrypted data, as long as the data is encrypted with an encryption scheme that is fully homomorphic.
One might say that a homomorphic encryption scheme is “malleable”, in the sense that the plaintext data can be modified while it is encrypted, while it is “inside the encryption box”. A useful, readable reference on homomorphic encryption is the article by Craig Gentry, “Computing Arbitrary Functions of Encrypted Data”, in the March 2010 issue of Communications of the ACM, available online here: http://crypto.stanford.edu/craig/easy-fhe.pdf. This article uses a physical analogy to describe homomorphic encryption. Encryption is like a lockbox: the sender puts his data inside a box for which only the user has a key, and then he sends the lockbox to the user; the user “decrypts” by unlocking the box. Homomorphic encryption is like a locked glovebox. It is like a lockbox in the sense that once something is locked inside, only the user with the secret key can remove it. However, the gloves allow anyone to manipulate or “process” objects while they remain securely inside a box.
Why is homomorphic encryption desirable, why would you want to let ciphertexts be malleable so that anyone can modify what is encrypted? Essentially, the answer is that there are many settings where you might want to let someone else process your data, but you don't want to give away access to your data—i.e., you want to keep your data private. Consider a search engine query (e.g., a Google search). You might like to get a response from Google, without revealing to Google exactly what your query is. If you have a fully homomorphic encryption scheme, this actually becomes possible. Suppose (the bits of) your query is π1, . . . , πt. You run KeyGen to get a key-pair (sk, pk) and you encrypt these bits under pk using the encryption scheme to get some ciphertexts ψ1, . . . , ψt that you send to Google. Now suppose that Google agrees to use fully homomorphic encryption to process encrypted queries. Google has some function ƒ, which can be represented as a boolean circuit C, that it uses to respond to queries. (This function ƒ depends on the bits of the query, on the bits of the (huge amount of) data that Google has on its servers, and on the particular algorithm that Google uses to respond to searches.) Google simply runs ψ←Evaluateε(pk, C, ψ1, . . . , ψt), and sends c to the user. (In practice, the response may consist of more than one ciphertext; in particular, it will if C has more than one output wire.) Finally, the user obtains C(π1, . . . , πt)←Decrypt(sk, ψ), which is exactly the response that it wanted from Google. But, due to the encryption, Google never learns any information about the query that it answered! Fully homomorphic encryption is also very useful in many cloud computing settings.
The notion of fully homomorphic encryption has been known for a long time. In 1978, Rivest, Adleman and Dertouzous suggested that such a scheme may be possible, referring to the notion as a privacy homomorphism, and they suggested some possible schemes, but these schemes were quickly found to be insecure—i.e., the ciphertexts did not actually hide the message well. (See R. Rivest, L. Adleman, and M. Dertouzos, “On data banks and privacy homomorphisms”, in Foundations of Secure Computation, pages 169-180, 1978.) Since that time, it has been a major open problem in cryptography to find a secure fully homomorphic encryption scheme.
(The notion of a “provably secure” encryption scheme will be known to those well-versed in the art, but may be a bit mysterious to outsiders. Roughly speaking, in modern cryptography, one is expected to prove that the security of a proposed cryptosystem is based on an established problem that is believed to be hard. For example, one might prove a statement like the following: if there is an attacker that can efficiently break this cryptosystem, then this attacker can be used as a subroutine to make an efficient algorithm that factors very large integers into their prime factors. Since it is widely assumed that no efficient algorithm for factoring large numbers exists, the above statement proves that the scheme is secure, under the assumption that factoring is “hard”. There are, of course, many other problems that are assumed to be hard, besides factoring.)
In the prior art, there have been provably secure encryption schemes that are partially homomorphic. For example, there are encryption schemes that are additively homomorphic. There are also schemes that are multiplicatively homomorphic. However, there are no schemes that are fully homomorphic. Unfortunately, if you have an encryption scheme that is only (say) additively homomorphic, it cannot be used (for example) to enable an encrypted Google search as described above, because Google's search function will be quite complicated, certainly not (even close to being) expressible by a sequence of addition operations. The same is true of encryption schemes that are only multiplicatively homomorphic (and not homomorphic over addition).
The cryptographic literature on homomorphic encryption is quite extensive, and indicative of how important the open problem of fully homomorphic encryption was. In fact, the first public-key encryption scheme, called RSA for its authors (R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. In Comm. of the ACM, 21:2, pages 120-126, 1978), was multiplicatively homomorphic: given an RSA public key (N, e) and ciphertexts c1=me1 mod N, . . . , ct=mte mod N, one can compute c=Πi=1t ci mod N=(Πi=1i mi)e mod N, a ciphertext that encrypts the product of the original plaintexts. (Possibly, this multiplicative homomorphism of RSA awakened Rivest, Adleman and Dertouzous to the notion of fully homomorphic encryption.) The first partially (additively in this case) homomorphic encryption scheme with a desirable property called “semantic security” against chosen plaintext attacks was by Goldwasser and Micali, “Probabilistic encryption and how to play mental poker keeping secret all partial information”, Proc. 14th Symposium on Theory of Computing: 365-377.
It is known that one can construct additively homomorphic encryption schemes from lattices or linear codes. The lattice-based scheme and the Reed-Solomon-code-based scheme allow multiplications, though with exponential expansion in ciphertext size. Ciphertexts implicitly contain an “error” that grows as ciphertexts are added together. Thus, ciphertexts output by Evaluate do not have the same distribution as ciphertexts output by Encrypt, and at some point the error may become large enough to cause incorrect decryption. For this reason, the homomorphism is sometimes referred to as a “pseudohomomorphism” or a “bounded homomorphism”.
There are schemes that use a singly homomorphic encryption scheme to construct a scheme that can perform more complicated homomorphic operations (T. Sander, A. Young, and M. Yung. Non-interactive cryptocomputing for NC1. In Proc. of FOCS '99, pages 554-567, 1999, and Y. Ishai and A. Paskin. Evaluating Branching Programs on Encrypted Data. In Proc. of TCC '07. Sanders, Young and Yung (SYY) show that one can use a circuit-private additively homomorphic encryption scheme to construct a circuit-private scheme that can handle arbitrary circuits, where the ciphertext size increases exponentially with the depth of the circuit. Their scheme may, therefore, feasibly evaluate NC1 circuits. Ishai and Paskin show how to evaluate branching programs, and with much smaller ciphertexts than SYY. In their scheme Evaluate outputs a ciphertext whose length is proportional to the length of the branching program. This remains true even if the size of the branching program is very large, e.g., super-polynomial. However, the computational complexity of their scheme is proportional to the size.
In more detail, Ishai and Paskin use a “leveled” approach to evaluate a branching program. A (deterministic) branching program (BP) P is defined by a DAG from a distinguished initial node in which each nonterminal node has two outgoing edges labeled 0 and 1, and where the terminal nodes also have labels.
Cryptographers have accumulated an assortment of applications for fully homomorphic encryption since then. However, until now, there was no viable construction of a fully homomorphic encryption scheme. In fact, previous homomorphic encryption schemes could compute only very simple functions.